/********************************************************************************
* @author: Liu  HZ
* @date: 2024/11/13
* @description: 
********************************************************************************/
#include "omp_demo.h"
#include "utils.h"
#include <vector>
#include <algorithm>
#include <thread>
#include <iostream>

using namespace std;

int main() {
    long long begin_time, end_time;
    const size_t array_size = 100000000; // 数组大小为1亿
    std::vector<uint64_t> large_array(array_size); // 填充大数组
    std::vector<uint64_t> result_indices; // 存储符合条件的索引

    begin_time = getCurrentTimeNanoseconds();
    for (size_t i = 0; i < array_size; ++i) {
        large_array[i] = i;
    }
    end_time = getCurrentTimeNanoseconds();
    std::cout << "数据生成-执行时间:" << static_cast<double>(end_time - begin_time) / 1e9 << std::endl;


    // 遍历数组，查找是1000000的倍数的数的位置
    begin_time = getCurrentTimeNanoseconds();
    for (size_t i = 0; i < array_size; ++i) {
        if (large_array[i] % 1000000 == 0) {
            result_indices.push_back(i); // 满足条件的索引存储到数组
        }
    }
    end_time = getCurrentTimeNanoseconds();
    std::cout << "单线程查找-执行时间:" << static_cast<double>(end_time - begin_time) / 1e9 << std::endl;

    cout << result_indices.size() << endl;
    // 输出结果
    for (size_t index: result_indices) {
        std::cout << index << " ";
    }
    std::cout << std::endl;
    result_indices.clear();

    const uint64_t num_intervals = std::thread::hardware_concurrency(); // 已知的子区间数量
    uint64_t interval_sizes[num_intervals]; // 存储每个区间的元素数量
    uint64_t interval_starts[num_intervals]; // 存储每个区间的开始位置

    interval_sizes[0] = large_array.size() / num_intervals;
    interval_starts[0] = 0;

    for (int i = 1; i < num_intervals; ++i) {
        interval_sizes[i] = interval_sizes[0];
        interval_starts[i] = interval_starts[i - 1] + interval_sizes[i - 1];
    }

    // 最后一个区间的结束位置需要特别处理，确保包含所有剩余元素
    interval_sizes[num_intervals - 1] += large_array.size() % num_intervals;

    begin_time = getCurrentTimeNanoseconds();
#pragma omp parallel for default(none) shared(large_array, interval_sizes, interval_starts, result_indices, num_intervals)
    for (size_t i = 0; i < num_intervals; ++i) {
        std::vector<size_t> local_indices; // 本地线程的索引存储
        for (size_t j = interval_starts[i]; j < interval_starts[i] + interval_sizes[i]; ++j) {
            if (condition(large_array[j])) {
                local_indices.push_back(j); // 满足条件的索引存储到本地数组
            }
        }

        // 将本地结果合并到全局数组中，需要线程安全
#pragma omp critical
        result_indices.insert(result_indices.end(), local_indices.begin(), local_indices.end());
    }

    std::sort(result_indices.begin(), result_indices.end());
    end_time = getCurrentTimeNanoseconds();
    std::cout << "并行查找-执行时间:" << static_cast<double>(end_time - begin_time) / 1e9 << std::endl;

    cout << result_indices.size() << endl;
    // 输出结果
    for (size_t index: result_indices) {
        std::cout << index << " ";
    }
    std::cout << std::endl;

    result_indices.clear();

    return 0;
}
